package codetop.huawei.T820;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: 18362
 * @Create: 2022-09-13 0:57:56 星期二
 */
class Solution {

    static class Trie {
        private Trie[] children = new Trie[26];
        private int[] flag = new int[26];

        boolean startWith(String s) {
            return startWith(s, 0);
        }

        private boolean startWith(String s, int cur) {
            int idx = s.charAt(cur) - 'a';
            if (flag[idx] == 0)
                return false;
            if (cur == s.length()-1)
                return flag[idx] == 1;
            return children[idx].startWith(s, cur+1);
        }

        void insert(String s) {
            insert(s, 0);
        }

        private void insert(String s, int cur) {
            int idx = s.charAt(cur) - 'a';
            if (cur == s.length()-1) {
                if (flag[idx] == 0)
                    flag[idx] = 2;
                return;
            }
            flag[idx] = 1;
            if (children[idx] == null)
                children[idx] = new Trie();
            children[idx].insert(s, cur+1);
        }
    }

    public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            String s = new StringBuilder(words[i]).reverse().toString();
            if (!set.contains(s)) {
                set.add(s);
                trie.insert(s);
            }
        }
        int res = 0;
        for (String s : set) {
            if (!trie.startWith(s))
                res += (s.length() + 1);
        }
        return res;
    }
}